import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 14:25
 */
public class test_2 {
    public static void main(String[] args) {
        int[] arr={2,5,1,7,10,6,9,4,3,8};
        System.out.println(Arrays.toString(arr));
        Merge_Sort(arr,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void Merge_Sort(int[] arr, int n) {
        for (int length = 1; length < n; length*=2) {
            MergeSort(arr,length,n);
        }
    }

    private static void MergeSort(int[] arr, int l, int n) {
        int j=0;
        for (j = 0; j+l*2-1 < n; j+=2*l) {
            Merge(arr,j,j+l-1,j+2*l-1);
        }
        if (j+l-1<n){
            Merge(arr,j,j+l-1,n-1);
        }
    }
    private static void Merge(int[] arr,int low,int mid,int hgigh){
        int[] tmp=new int[hgigh-low+1];
        int f1=low;
        int m1=mid;
        int f2=mid+1;
        int f3=0;
        while (f1<=m1&&f2<=hgigh){
            if (arr[f1]<=arr[f2]){
                tmp[f3]=arr[f1];
                f1++;
                f3++;
            }else {
                tmp[f3]=arr[f2];
                f2++;
                f3++;
            }
        }
        while (f1<=mid){
            tmp[f3]=arr[f1];
            f1++;
            f3++;
        }
        while (f2<=hgigh){
            tmp[f3]=arr[f2];
            f2++;
            f3++;
        }
        f3=0;
        for (int i = low; i <=hgigh ; i++) {
            arr[i]=tmp[f3];
            f3++;
        }
    }
}
